
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2010. -- [Ceoi2010]bodyguard -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2010: [Ceoi2010]bodyguard</h2><span class=green>Time Limit: </span>100 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>52&nbsp;&nbsp;<span class=green>Solved: </span>25<br>[<a href='submitpage.php?id=2010'>Submit</a>][<a href='problemstatus.php?id=2010'>Status</a>][<a href='bbs.php?id=2010'>Discuss</a>]</center><h2>Description</h2><div class=content>为保证会场安全，专家确定了每一行每一列的保镖数，这个信息以一种压缩的形式给出。确定是否有可能实现这样一种方案，在每行每列安排确定数量的保镖。假设座位最初都是空的，也就是说保安可以被安排在任意一个座位上。 
题目等价于已知一个01矩阵的每行、每列各有多少个1，问这样的矩阵是否存在。
输入数据归纳为：
有R个正整数对 A1、B1，A2 、B2，……， AR、BR 
表示这个01矩阵一共有 B1+B2+…+BR行，其中有Bi 个行都含有 Ai个1。
同样的，有C个正整数对 Pi和Qi 来表示列的信息。
限制条件：按行和按列计算的总保镖数相等</div><h2>Input</h2><div class=content>The input begins with the description of the rows. The first line of the input contains one positive integer R: the
number of groups of rows. R lines follow. Each of these lines contains 2 positive integers: the required number
of bodyguards in each row of the group and the number of rows that form the group.
This is followed by the description of column groups. The next line contains one positive integer C: the number
of groups of columns. C lines follow. Each of these lines contains 2 positive integers: the required number of
bodyguards in each column of the group and the number of columns that form the group.

You may assume that the total number of bodyguards required by row constrains is the same as the total
number of bodyguards required by column constraints. You may assume that this total number of bodyguards
is at most 10^18.
You may assume that all numbers are positive integers that do not exceed 10^9 .
You may assume 1<= R,C <= 200000 that  .
Several batches of test cases, worth a total of 50 points, satisfy the following criteria:
the total number of rows in the auditorium will be at most 2000
the total number of columns in the auditorium will be at most 2000
the total number of bodyguards will be at most  .
</div><h2>Output</h2><div class=content>Output a single line with the number "1" if the constraints are satisfiable and the number "0" otherwise (quotes
for clarity).</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>2<br />
2 1<br />
1 2<br />
1<br />
2 2</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>1</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=2010'>Submit</a>][<a href='problemstatus.php?id=2010'>Status</a>][<a href='bbs.php?id=2010'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
